package x.y.z;

import java.util.HashMap;
import java.util.Map;

public class LeetCode_0076 {
    public String minWindow(String s, String t) {
        int start = 0;
        int minLen = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;

        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> windows = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            needs.put(ch, needs.getOrDefault(ch, 0) + 1);
        }

        int matchs = 0;

        while (right < s.length()) {
            char c1 = s.charAt(right);
            if (needs.containsKey(c1)) {
                windows.put(c1, windows.getOrDefault(c1, 0) + 1);
                if (windows.get(c1).equals(needs.get(c1))) {
                    matchs++;
                }
            }
            right++;

            while (matchs == needs.size()) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char c2 = s.charAt(left);
                if (needs.containsKey(c2)) {
                    windows.put(c2, windows.getOrDefault(c2, 0) - 1);
                    if (windows.get(c2) < needs.get(c2)) {
                        matchs--;
                    }
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}
